package com.wtgroup.demo.leetcode.org_bytedance;

public class Q_搜索旋转排序数组 {
    public static void main(String[] args) {
        // int[] arr = {4, 5, 6, 7, 0, 1, 2};
        int[] arr = {3, 1};
        int target = 1;
        Q_搜索旋转排序数组 exe = new Q_搜索旋转排序数组();
        int res = exe.search(arr, target);
        System.out.println(res);
    }

    /*
    * case1: left<=mid
    *   left<=target<mid 必在左, 否则在右.
    *   无旋转(或称作全体旋转)时, 只会在case1中.
    * case2: !(left<=mid)
    *   mid<target<=right 必在右, 否则在左.
    * */

    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n-1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
                // left<=target<mid => 必在左侧
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            } else {
                // mid<target<=right => 必在右侧
                if((nums[mid] < target && target <= nums[right])) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
        }

        return -1;
    }

}
